package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3


/**
 * 1038. 从二叉搜索树到更大和树
 * https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/description
 *
 * 同 538. 把二叉搜索树转换为累加树
 * https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
 *
 * ```
 * 1038. 从二叉搜索树到更大和树
 * 给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
 * 提醒一下， 二叉搜索树 满足下列约束条件：
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树
 *
 * 示例 1：
 * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 *
 * 示例 2：
 * 输入：root = [0,null,1]
 * 输出：[1,null,1]
 *
 * 提示：
 * 树中的节点数在 [1, 100] 范围内。
 * 0 <= Node.val <= 100
 * 树中的所有值均 不重复 。
 * ```
 */
class leetcode_1038 {
    @Test
    fun test_2() {
        val root = TreeNode(0)
        root.right = TreeNode(1)

        val actual = bstToGst(root)
        val expected = arrayListOf(1, null, 1)
        Assert.assertEquals(expected.toString(), printLevelOrder3(actual).toString())
    }

    private fun bstToGst(root: TreeNode?): TreeNode? {
        /**
        题型： 二叉树的后序遍历（特殊：右中左）+ Pre 指针法

        思路：
        中：若pre 不为空，则 当前节点 + pre 节点值，然后用prev 记录上一个节点。
         */
        f(root)
        return root
    }

    private var pre: TreeNode? = null
    fun f(root: TreeNode?) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (root == null) {
            return
        }
        // 3 确定单层递归的处理逻辑：中序遍历（右中左）
        // 右
        f(root.right)

        // 中
        pre?.let {
            // println("${root.`val`}, prev = ${it.`val`} -> ${(root.`val`  + it.`val`)}")
            root.`val` = root.`val` + it.`val`
        }
        pre = root

        // 左
        f(root.left)
    }
}